package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了81.33%的用户
内存消耗：6 MB, 在所有 Go 提交中击败了24.10%的用户
 */
func maximalRectangle(matrix [][]byte) int {

	if len(matrix) == 0 || len(matrix[0]) == 0 { return 0 }
	n, m := len(matrix), len(matrix[0])

	f := make([][]int, n)
	for i := 0; i < n; i++ { f[i] = make([]int, m) }

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if matrix[i][j] == '1' {
				if i > 0 {
					f[i][j] = f[i - 1][j] + 1
				} else {
					f[i][j] = 1
				}
			}
		}
	}

	res := 0
	for i := 0; i < n; i++ {
		res = max(res, find(f[i]))
	}
	return res
}

func find(h []int) int {

	n := len(h)
	l, r := make([]int, n), make([]int, n)

	stk := []int{}
	for i := 0; i < n; i++ {
		for len(stk) > 0 && h[i] <= h[stk[len(stk) - 1]] { stk = stk[:len(stk) - 1] }
		if len(stk) > 0 {
			l[i] = stk[len(stk) - 1]
		} else {
			l[i] = -1
		}
		stk = append(stk, i)
	}

	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && h[i] <= h[stk[len(stk) - 1]] { stk = stk[:len(stk) - 1] }
		if len(stk) > 0 {
			r[i] = stk[len(stk) - 1]
		} else {
			r[i] = n
		}
		stk = append(stk, i)
	}

	res := 0
	for i := 0; i < n; i++ {
		res = max(res, h[i] * (r[i] - l[i] - 1))
	}
	return res
}

// 求最大值
func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {

	matrix := [][]byte{
		{'1', '0', '1', '0', '0'},
		{'1', '0', '1', '1', '1'},
		{'1', '1', '1', '1', '1'},
		{'1', '0', '0', '1', '0'},
	}
	fmt.Println(maximalRectangle(matrix))
}
